//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "type_traits.h"
#include "allocator.h"
#include "iterator.h"
#include "forward.h"


FC_NAMESPACE_BEGIN

/*
template <class T>
struct list_node_base
{
	//list_node_base* prev;
	//list_node_base* next;
	T* prev;
	T* next;

	list_node_base()
		{
			prev = next = (T*)this;
		}

	//void link( list_node_base* n )
	void link( T* n )
	{
		prev = n->prev;
		next = n;
		prev->next = n->prev = (T*)this;
	}

	void unlink()
	{
		prev->next = next;
		next->prev = prev;
	}

	static void reverse( T* pivot )
	{
		T* p = pivot;
		do {
			fc::swap( p->next, p->prev );
			p = p->prev;
		}
		while( p != pivot );
	}

	void splice( list_node_base* first, list_node_base* last )
	//void splice( T* first, T* last )
	{
		prev->next  = (T*)first;
		first->prev->next = (T*)last;
		last->prev->next  = (T*)this;

		list_node_base* p = prev;
		prev = last->prev;
		last->prev = first->prev;
		first->prev = (T*)p;
	}

	static void swap( list_node_base& a, list_node_base& b )
	{
		fc::swap( a, b );

		//if a node is self-linked (empty), then we have to re-link to self.
		//todo: optimize
		if( a.next == a.prev && a.next == &b ) a.next = a.prev = (T*)&a;
		if( b.next == b.prev && b.next == &a ) b.next = b.prev = (T*)&b;
		a.prev->next = a.next->prev = (T*)&a;
		b.prev->next = b.next->prev = (T*)&b;
	}

	void swap( list_node_base& x )
	{
		swap( *this, x );
	}

};


template <class T>
struct list_node : public list_node_base< list_node<T> >
{
	typedef list_node<T>	node_type;
	typedef T				value_type;
	list_node() {}
	explicit list_node( const T& value ): list_node_base< list_node<T> >(), value(value) {}


	value_type value;
};
*/


// this debugging crap will be fixed later on...

template <class T>
struct list_node
{
	typedef list_node<T>	node_type;
	typedef T				value_type;

	list_node() {}
	explicit list_node( const T& value ) : value(value) {}

	node_type* prev;
	node_type* next;
	value_type value;

	void link( node_type* n )
	{
		prev = n->prev;
		next = n;
		prev->next = n->prev = (node_type*)this;
	}

	void unlink()
	{
		prev->next = next;
		next->prev = prev;
	}

	static void reverse( node_type* pivot )
	{
		node_type* p = pivot;
		do {
			fc::swap( p->next, p->prev );
			p = p->prev;
		}
		while( p != pivot );
	}

	void splice( node_type* first, node_type* last )
	//void splice( T* first, T* last )
	{
		prev->next = first;
		first->prev->next = last;
		last->prev->next = this;

		node_type* p = prev;
		prev = last->prev;
		last->prev = first->prev;
		first->prev = p;
	}

	static void swap( node_type& a, node_type& b )
	{
		fc::swap( a, b );

		//if a node is self-linked (empty), then we have to re-link to self.
		//todo: optimize
		if( a.next == a.prev && a.next == &b ) a.next = a.prev = (node_type*)&a;
		if( b.next == b.prev && b.next == &a ) b.next = b.prev = (node_type*)&b;
		a.prev->next = a.next->prev = (node_type*)&a;
		b.prev->next = b.next->prev = (node_type*)&b;
	}

	void swap( node_type& x )
	{
		swap( *this, x );
	}

};



// list_iterator

template <class T>
class list_iterator
{
public:
	//iterator_category - std required
	typedef std::bidirectional_iterator_tag	iterator_category;
	typedef bidirectional_iterator_tag		iterator_type;

	typedef T							value_type;
	typedef T*							pointer;
	typedef T&							reference;
	typedef ptrdiff_t					difference_type;
	typedef list_node<T>				node_type;
	typedef list_iterator<T>			this_type;

	template <class Type, class Allocator> friend class list;

	list_iterator() : ptr(0) {}
	list_iterator( const node_type* p ) : ptr(const_cast<node_type*>(p)) {}

	template <class U>
	list_iterator( list_node<U>* p ) : ptr((node_type*)p) {}

	template <class U>
	list_iterator( const list_iterator<U>& i ) : ptr((node_type*)i.base()) {}
	//list_iterator( const list_iterator<T>& i ) : ptr((node_type*)i.base()) {}

	//template <class U> bool operator ==( const list_iterator<U>& it ) const { return ptr == it.ptr; }
	//template <class U> bool operator !=( const list_iterator<U>& it ) const { return ptr != it.ptr; }
	bool operator ==( const list_iterator& it ) const { return ptr == it.ptr; }
	bool operator !=( const list_iterator& it ) const { return ptr != it.ptr; }

	reference operator*() const { return ptr->value; }
	pointer operator->() const { return &ptr->value; }

	node_type* base() const { return ptr; }

	this_type& operator ++() { ptr = (node_type*)ptr->next; return *this; }
	this_type& operator --() { ptr = (node_type*)ptr->prev; return *this; }
	this_type  operator ++(int) { this_type temp(*this); ++(*this); return temp; }
	this_type  operator --(int) { this_type temp(*this); --(*this); return temp; }

	this_type operator +( ptrdiff_t n ) { this_type temp(*this); fc::advance( temp, n ); return temp; }
	this_type operator -( ptrdiff_t n ) { this_type temp(*this); fc::advance( temp, -n ); return temp; }
	ptrdiff_t operator -( const list_iterator& it ) { return fc::distance(it, *this); }

protected:
	node_type*	ptr;

};




// list_base

template <class T, class Allocator>
class list_base
{
public:
	typedef list_base<T, Allocator>					this_type;
	typedef Allocator								allocator_type;
	typedef list_node<T>							node_type;
	typedef size_t									size_type;

	list_base() : m_allocator(), m_head(), m_size(0)
		{
			init_head();
		}

	explicit list_base( const allocator_type& alloc )
		: m_allocator(alloc), m_head(), m_size(0)
		{
			init_head();
		}

	~list_base()
		{
			clear();
		}

	allocator_type& get_allocator() { return m_allocator; }
	const allocator_type& get_allocator() const { return m_allocator; }
	void set_allocator( const allocator_type& alloc ) { m_allocator = alloc; }

	void clear()
	{
		node_type* first = (node_type*)m_head.next;
		node_type* last = (node_type*)&m_head;
		for( node_type* next; first != last; first = next )
		{
			next = first->next;
			destroy_node(first);
		}

		m_size = 0;
		init_head();
	}

protected:
	void init_head()
	{
		m_head.prev = m_head.next = (node_type*)&m_head;
	}

	node_type* create_node( const T& value )
	{
		node_type* ptr = (node_type*)m_allocator.allocate( sizeof(node_type) );
		fc::construct( &ptr->value, value );
		//new (ptr) node_type(value);
		return ptr;
	}

	void destroy_node( node_type* n )
	{
		fc::destroy( &n->value );
		//n->~node_type();
		m_allocator.deallocate( n, sizeof(node_type) );
	}

	allocator_type	m_allocator;
	//list_node_base<node_type>	m_head;
	node_type m_head;
	size_type m_size;

};



// list

template <class T, class Allocator>
class list : public list_base<T, Allocator>
{
public:
	typedef Allocator								allocator_type;
	typedef list<T, Allocator>						this_type;
	typedef list_base<T, Allocator>					base_type;
	typedef list_node<T>							node_type;
	typedef size_t									size_type;
	typedef T										value_type;
	typedef T*										pointer;
	typedef const T*								const_pointer;
	typedef T&										reference;
	typedef const T&								const_reference;
	typedef list_iterator<T>						iterator;
	typedef list_iterator<const T>					const_iterator;
	typedef fc::reverse_iterator<iterator>			reverse_iterator;
	typedef fc::reverse_iterator<const_iterator>	const_reverse_iterator;

	using base_type::create_node;
	using base_type::destroy_node;
	using base_type::clear;

	using base_type::m_allocator;
	using base_type::m_head;
	using base_type::m_size;

	list() : base_type()
		{
		}

	explicit list( const allocator_type& alloc )
		: base_type(alloc)
		{
		}

	template <class InputIterator>
	list( InputIterator first, InputIterator last )
		: base_type()
		{
			assign( first, last );
		}

	list( const list& l )
		: base_type()
		{
			assign( l.begin(), l.end() );
		}

	iterator		begin()			{ return iterator((node_type*)(m_head.next)); }
	const_iterator	begin() const	{ return const_iterator((node_type*)(m_head.next)); }
	iterator		end()			{ return iterator((node_type*)&m_head); }
	const_iterator	end() const		{ return const_iterator((node_type*)&m_head); }
	reverse_iterator		rbegin()		{ return reverse_iterator(end()); }
	const_reverse_iterator	rbegin() const	{ return const_reverse_iterator(end()); }
	reverse_iterator		rend()			{ return reverse_iterator(begin()); }
	const_reverse_iterator	rend() const	{ return const_reverse_iterator(begin()); }

	reference		front()			{ FC_ASSERT(!empty()); return ((node_type*)m_head.next)->value; }
	const_reference	front() const	{ FC_ASSERT(!empty()); return ((node_type*)m_head.next)->value; }
	reference		back()			{ FC_ASSERT(!empty()); return ((node_type*)m_head.prev)->value; }
	const_reference	back() const	{ FC_ASSERT(!empty()); return ((node_type*)m_head.prev)->value; }

	bool empty() const		{ return m_head.next == &m_head; }
	size_t size() const		{ return m_size; }

	void resize( size_t n, const T& value = T() )
	{
		if( n < m_size )
		{
			iterator it = end();
			while( n < m_size ) ++n, --it;
			erase( it, end() );
		}
		else if( n > m_size )
			insert( end(), n - m_size, value );
	}

	template <class InputIterator>
	void assign( InputIterator first, InputIterator last )
	{
		node_type* current = (node_type*)m_head.next;
		for( ; first != last && current != (node_type*)&m_head; ++first )
		{
			current->value = *first;
			current = (node_type*)current->next;
		}

		if( first != last )
			InsertIter( iterator(current), first, last );
		else
			Erase( current, (node_type*)&m_head );
	}

	void assign( size_t n, const T& value )
	{
		node_type* current = (node_type*)m_head.next;
		for( ; n && current != (node_type*)&m_head; --n )
		{
			current->value = value;
			current = (node_type*)current->next;
		}

		if( n != 0 )
			insert( iterator(current), n, value );
		else
			Erase( current, (node_type*)&m_head );
	}

	iterator insert( iterator pos, const T& value )
	{
		node_type* p = Insert( (node_type*)pos.ptr, value );
		return iterator(p);
	}

	void insert( iterator pos, size_t n, const T& value )
	{
		for( ; n != 0; --n )
			Insert( pos.ptr, value );
	}

	template <class InputIterator>
	void insert( iterator pos, InputIterator first, InputIterator last )
	{
		InsertDispatch( pos, first, last,
			typename fc::is_integral<InputIterator>::type() );
	}

	iterator erase( iterator pos )
	{
		node_type* next = (node_type*)pos.ptr->next;
		Erase( pos.ptr );
		return iterator(next);
	}

	iterator erase( iterator first, iterator last )
	{
		//while( first != last )
		//	first = erase(first);
		Erase( first.ptr, last.ptr );
		return iterator(last);
	}

	void push_front( const T& value = T() )
	{
		Insert(m_head.next, value);
	}

	void pop_front()
	{
		FC_ASSERT(!empty());
		Erase( (node_type*)m_head.next );
	}

	void push_back( const T& value = T() )
	{
		Insert(&m_head, value);
	}

	void pop_back()
	{
		FC_ASSERT(!empty());
		Erase( (node_type*)m_head.prev );
	}

	void splice( iterator pos, this_type& l )
	{
		splice( pos, l, l.begin(), l.end() );
	}

	void splice( iterator pos, this_type& l, iterator i )
	{
		splice( pos, l, i, iterator(i.ptr->next) );
	}

	void splice( iterator pos, this_type& l, iterator first, iterator last )
	{
		if( m_allocator == l.m_allocator )
		{
			size_t n = (size_t)fc::distance(first, last);
			pos.ptr->splice( (node_type*)first.ptr, (node_type*)last.ptr );
			l.m_size -= n;
			m_size += n;
		}
		else
		{
			insert( pos, first, last );
			l.erase( first, last );
		}
	}

	void reverse()
	{
		node_type::reverse( (node_type*)&m_head );
	}

	void remove( const T& value )
	{
		node_type* first = (node_type*)m_head.next;
		node_type* last = (node_type*)&m_head;
		for( node_type* prev = last; first != last; prev = first, first = first->next )
			if( first->value == value )
				Erase(first), first = prev;

		/*
		//todo: optimize this
		iterator it = fc::remove( begin(), end(), value );
		erase( it, end() );
		*/
	}

	template <class Predicate>
	void remove_if( Predicate predicate )
	{
		node_type* first = m_head.next;
		node_type* last = &m_head;
		for( node_type* p; first != last; first = p )
		{
			p = first->next;
			if( predicate(first->value) )
				Erase(first);
		}
	}

	template <class BinaryPredicate>
	void unique( BinaryPredicate predicate )
	{
		node_type* first = m_head.next;
		node_type* last = &m_head;
		if( first != last )
		{
			for( node_type* next = first->next; next != last; first = next, next = next->next )
				if( predicate(first->value, next->value) )
					Erase( next ), next = first;
		}

		/*
		iterator it = fc::unique( begin(), end(), comp );
		if( it != end() )
			erase( it, end() );
			*/
	}

	void unique()
	{
		unique( equal_to<T>() );
	}

	void merge( this_type& l, iterator first, iterator last ) { merge( l, first, last, fc::less<T>() ); }
	void merge( this_type& l ) { merge( l, l.begin(), l.end(), fc::less<T>() ); }

	template <class Compare> void merge( this_type& l, Compare compare ) { merge( l, l.begin(), l.end(), compare ); }
	template <class Compare> FC_NO_INLINE
	void merge( this_type& l, iterator first, iterator last, Compare compare )
	{
		Merge( begin(), end(), first, last, compare );
		m_size += l.m_size;
		l.m_size = 0;
	}

	template <class Compare> FC_NO_INLINE
	void sort( Compare compare )
	{
		if( m_size < 2 )
			return;

		// We do an in-place sort on the list here.
		// This has the benefit of being fast when compared to 
		// other sorting methods so long as the list is reasonably sized,
		// as you would expect for games or other real-time applications,
		// but can still be used on stupidly large lists as well.
		// Note that we will never create any temporary list objects or
		// allocations, so it is safe to use regardless of custom allocator.

		// todo: optimize this for large lists.

		node_type newHead;
		node_type* pNewHead = &newHead;
		pNewHead->next = pNewHead->prev = pNewHead;

		node_type* first = m_head.next;
		node_type* last = &m_head;
		for( node_type* next; first != last; first = next )
		{
			next = first->next;

			first->prev->next = first->next;
			first->next->prev = first->prev;
			first->next = first->prev = first;

			node_type* first2 = pNewHead->next;
			node_type* last2 = pNewHead;
			for( ; first2 != last2; first2 = first2->next )
			{
				if( compare(first->value, first2->value) )
				{
					first->link( first2 );
					break;
				}
			}

			if( first2 == last2 )
				first->link( last2 );
		}

		// link back to head
		m_head.next = pNewHead->next;
		m_head.prev = pNewHead->prev;
		m_head.next->prev = m_head.prev->next = &m_head;

	}

	void sort()
	{
		sort( less<T>() );
	}

	this_type& operator =( const this_type& l )
	{
		if( this != &l )
			assign( l.begin(), l.end() );

		return *this;
	}

	void swap( this_type& x )
	{
		if( m_allocator == x.m_allocator )
		{
			fc::swap( m_size, x.m_size );
			node_type::swap( m_head, x.m_head );
		}
		else
		{
			this_type temp(*this);
			*this = x;
			x = temp;
		}
	}

protected:
	template <typename InputIterator>
	void InsertDispatch( iterator pos, InputIterator first, InputIterator last, const false_type& )
	{
		InsertIter( pos, first, last );
	}

	template <class Integral>
	inline void InsertDispatch( iterator it, Integral n, Integral value, const true_type& )
	{
		insert( it, (size_t)n, (T)value );
	}

	template <typename InputIterator>
	void InsertIter( iterator pos, InputIterator first, InputIterator last )
	{
		for( node_type* p = pos.ptr; first != last; ++first )
			Insert(p, *first);
	}

	node_type* Insert( node_type* pos, const T& value )
	{
		node_type* p = create_node(value);
		p->link(pos);
		++m_size;
		return p;
	}

	void Erase( node_type* first, node_type* last )
	{
		size_t n(0);
		node_type* p = first->prev;
		for( node_type* next; first != last; first = next, ++n )
		{
			next = first->next;
			destroy_node(first);
		}

		p->next = last;
		last->prev = p;
		m_size -= n;
	}

	void Erase( node_type* pos )
	{
		pos->unlink();
		destroy_node(pos);
		--m_size;
	}

	template <class Compare>
	void Merge( iterator first1, iterator last1, iterator first2, iterator last2, Compare compare )
	{
		while( (first1 != last1) && (first2 != last2) )
		{
			if( compare(*first2, *first1) )
			{
				node_type* p1 = (node_type*)first2.ptr;
				//while( (++first2 != last2) && compare(*first2, *first1) )
				//	; ++first2;

				//
				while( (++first2 != last2) && compare(*first2, *first1) )
					; //++first2;
				//

				first1.ptr->splice( p1, (node_type*)first2.ptr );
			}
			else
				++first1;
		}

		// append remaining to end of sequence.
		if( first2 != last2 )
			last1.ptr->splice( (node_type*)first2.ptr, (node_type*)last2.ptr );
	}

};




// global list operators

template <class T, class Allocator> inline
	void swap( const list<T, Allocator>& a, const list<T, Allocator>& b )
	{
		a.swap(b);
	}

template <class T, class A1, class A2> inline
	bool operator ==( const list<T, A1>& a, const list<T, A2>& b )
	{
		return( &a == &b || (a.size() == b.size() && fc::equal(a.begin(), a.end(), b.begin())) );
	}

template <class T, class A1, class A2> inline
	bool operator !=( const list<T, A1>& a, const list<T, A2>& b )
	{
		return !(a == b);
	}

template <class T, class A1, class A2> inline
	bool operator <( const list<T, A1>& a, const list<T, A2>& b )
	{
		return fc::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
	}

template <class T, class A1, class A2> inline
	bool operator >( const list<T, A1>& a, const list<T, A2>& b )
	{
		return b < a;
	}

template <class T, class A1, class A2> inline
	bool operator <=( const list<T, A1>& a, const list<T, A2>& b )
	{
		return !(b < a);
	}

template <class T, class A1, class A2> inline
	bool operator >=( const list<T, A1>& a, const list<T, A2>& b )
	{
		return !(a < b);
	}


FC_NAMESPACE_END

